#include <iostream>
#include <vector>
#include <memory>
#include <map>
#include <limits.h>

using namespace std;

template<typename KT, typename DT>
class BinomialHeap {
private:
	struct node {
		DT data;
		KT key;
		int degree;
		weak_ptr<node> parent;
		shared_ptr<node> rsibling;
		shared_ptr<node> lchild;
		node(KT k, DT d) {
			data = d;
			key = k;
			degree = 0;
		};
		node(){

		}
	};
public:
	BinomialHeap(){
		root = nullptr;
	}
	BinomialHeap(KT k, DT d) {
		node a(k, d);
		shared_ptr<node> p(new node(a));
		root = p;
	}
	BinomialHeap(shared_ptr<node> tree) {
		root = tree;
	}
	shared_ptr<node> root;
	shared_ptr<node> getMinimum() { //ìèíèìóì èùåòñÿ ñðåäè ñïèñêà êîðíåé
		KT min = root->key;
		shared_ptr<node> currentNode = root;
		shared_ptr<node> minNote = root;
		for (shared_ptr<node> i = root->rsibling; i != nullptr; i = currentNode->rsibling) {
			if (i->key < min) {
				min = i->key;
				minNote = i;
			}
		}
		return minNote;
	}
	shared_ptr<node> extractMin() { //óäàëåíèå âåðøèíû ñ íàèìåíüøèì êëþ÷îì
		KT min = INT_MAX;
		shared_ptr<node> x = nullptr;
		shared_ptr<node> xBefore = nullptr;
		shared_ptr<node> curx = root;
		shared_ptr<node> curxBefore = nullptr;

		while (curx != nullptr) { //íàõîäèì âåðøèíó ñ ìèíèìàëüíûì 
			if (curx->key < min) {
				min = curx->key;
				x = curx;
				xBefore = curxBefore;
			}
			curxBefore = curx;
			curx = curx->rsibling;
		}

		if (xBefore == nullptr) {
			root = x->rsibling;
		}
		else {
			xBefore->rsibling = x->rsibling;
		}

		BinomialHeap H;
		weak_ptr<node> a;
		curx = x->lchild;

		while (curx != nullptr) {
			curx->parent = a;           // ìåíÿåì óêàçàòåëü íà ðîäèòåëÿ óçëà curx 
			H.root = curx;
			curx = curx->rsibling;      // ïåðåõîä ê ñëåäóþùåìó ðåáåíêó 
			H.root->rsibling = nullptr;
			*this = (*this).merge(H); //êàæäóþ êó÷ó èç ñïèñêà ñ íàøèì îñòàâøåéñÿ êó÷åé
		}
		return x;
	}
	BinomialHeap merge(BinomialHeap& other){ //îáúåäèíåíèå äâóõ êó÷
		if (root == nullptr){ //åñëè îäíà èç êó÷ ïóñòà, âîçâðàùàåì äðóãóþ
			return other;
		}
		if (other.root == nullptr){
			return *this;
		}

		BinomialHeap H;
		H.root = nullptr;                     // H  ðåçóëüòàò ñëèÿíèÿ 
		shared_ptr<node> curH;                    // ñëèÿíèå êîðíåâûõ ñïèñêîâ 
		shared_ptr<node> curH1 = root;           //áóäåì èäòè ïî êîðíÿì êó÷è, ñðàâíèâàÿ ñòåïåíü, è îáúåäèíÿÿ êó÷è ñ îäèíàêîâîé ñòåïåíüþ
		shared_ptr<node> curH2 = other.root;
		while ((curH1 != nullptr) && (curH2 != nullptr)) {
			if (curH1->degree < curH2->degree) { //åñëè ñòåïåíü êó÷è èç ïåðâîãî ñïèñêà ìåíüøå, òî äîáàâëÿåì åå â ðåçóëüòèðóþùóþ
				if (curH == nullptr){ //åñëè â ðåçóëüòèðóþùåì ñïèñêå êó÷ ïîêà íè÷åãî íåò, òî óñòàíàâëèâàåì êîðåíü
					curH = curH1; //òåïåðü òåêóùàÿ âåðøèíà â ðåçóëüòèðóþùåì ñïèñêå -- êîðåíü êó÷è èç ïåðâîãî ñïèñêà
					H.root = curH; //îíà æå áóäåò êîðíåì
				}
				else {
					curH->rsibling = curH1; //åñëè â ñïèñêå óæå åñòü êó÷è, äîáàâèì ê íèì áðàòà ñïðàâà
					curH = curH->rsibling; //òåêóùåé êó÷åé ðåçóëüòèðóþùåãî ñïèñêà ñäåëàåì ýòîãî áðàòà
				}
				curH1 = curH1->rsibling; //ïðîõîäèì ê ñëåäóþùåé êó÷å â ïåðâîì ñïèñêå
			}
			else{                       //åñëè ñòåïåíü êó÷è èç ïåðâîãî ñïèñêà íå ìåíüøå
				if (curH == nullptr){   //è àíàëîãè÷íî äîáàâëÿåì â îáùèé ñïèñîê êó÷è èç âòîðîãî ñïèñêà
					curH = curH2;
					H.root = curH;
				}
				else {
					curH->rsibling = curH2;
					curH = curH->rsibling;
				}
				curH2 = curH2->rsibling;
			}
		}
		//â ñëó÷àå, åñëè îäèí ñïèñîê çàêîí÷èëñÿ, äîáàâèì âñå îñòàâøèåñÿ êó÷è èç äðóãîãî â ðåçóëüòèðóþùèé ñïèñîê
		if (curH1 == nullptr) {
			while (curH2 != nullptr) {
				curH->rsibling = curH2;
				curH2 = curH2->rsibling;
			}
		}
		else{
			while (curH1 != nullptr){
				curH->rsibling = curH1;
				curH1 = curH1->rsibling;
			}
		}
		//òàê ó íàñ ïîëó÷èëñÿ ñïèñîê êó÷ â ïîðÿäêå íåóáûâàíèÿ èõ ñòåïåíè
		shared_ptr<node> pred = nullptr;
		curH = H.root;                // îáúåäèíåíèå äåðåâüåâ îäíîé ñòåïåíè
		while (curH->rsibling != nullptr){ //ïîêà â ñïèñêå íå êîí÷àòñÿ êó÷è
			if (curH->degree == curH->rsibling->degree) { //åñëè ñòåïåíü äâóõ êó÷ â ñïèñêå ñîâïàëà
				if (curH->key > curH->rsibling->key){ //íàõîäèì ìèíèìàëüíûé êëþ÷ â êîðíå èç ýòèõ äâóõ êó÷
					curH->parent = curH->rsibling; //ðîäèòåëåì êîðíÿ êó÷è ñ áîëüøèì êëþ÷åì áóäåò êîðåíü âòîðîé êó÷è
					shared_ptr<node> tmp(curH->rsibling); //êîïèðóåì óêàçàòåëü äëÿ óäîáñòâà
					curH->rsibling = curH->rsibling->lchild; //áðàòîì äåëàåì ëåâîãî ðåáåíêà
					tmp->lchild = curH; //ðåáåíêîì âòîðîé êó÷è äåëàåì ïåðâóþ
					curH = tmp; //òåêóùåé êó÷åé äåëàåì âîòîðóþ
					curH->degree = curH->degree + 1; //óâåëè÷èâàåì ñòåïåíü êó÷è
					if (pred == nullptr) {
						H.root = curH;
					}
					else {
						pred->rsibling = curH;
					}
					continue;
				}
				else {                             //åñëè ó âòîðîé êó÷è êëþ÷ áîëüøå, äåëàåì åãî ðåáåíêîì ïåðâîé
					curH->rsibling->parent = curH; //ó âòîðîé êó÷è ðîäèòåëü -- ïåðâàÿ êó÷à
					shared_ptr<node> tmp(curH->rsibling->rsibling); //àíàëîãè÷íî 
					curH->rsibling->rsibling = curH->lchild;
					curH->lchild = curH->rsibling;
					curH->rsibling = tmp;
					curH->degree = curH->degree + 1;
					if (pred == nullptr) {
						H.root = curH;
					}
					else {
						pred->rsibling = curH;
					}
					continue;
				}
			}
			else {
				pred = curH;
				curH = curH->rsibling;
			}
		}
		return H;
	}
	void insert(KT key, DT data) { //äîáàâëåíèå ýëåìåíòà
		if (root == nullptr){
			BinomialHeap a(key, data);
			*this = a;
		}
		else { //ñîçäàåì êó÷ó èç âåðøèíû
			BinomialHeap other(key, data);
			*this = other.merge(*this); //îáúåäèíÿåì äâå êó÷è
		}
	}
	void decreaseKey(shared_ptr<node> x, KT k) {
		if (k > x->key){                    // проверка на то, что текущий ключ x не меньше передаваемого ключа k  
			return;
		}
		x->key = k;
		shared_ptr<node> y = x;
		shared_ptr<node> z = y->parent.lock();
		while ((z != nullptr) && (y->key < z->key)){ // поднимаем  x с новым ключом k, пока это значение меньше значения в родительской вершине 
			int d, k;
			d = z->data;
			k = z->key;
			z->data = y->data;
			z->key = y->key;
			y->data = d;
			y->key = k;
			y = z;
			z = z->parent.lock();
		}
	}
	void deleteNode(shared_ptr<node> x) {
		decreaseKey(x, -INT_MAX); // óìåíüøåíèå êëþ÷à äî ìèíèìàëüíî âîçìîæíîãî çíà÷åíèÿ 
		extractMin();           // óäàëåíèå "âñïëûâøåãî" ýëåìåíòà
	}
};